{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for graph partition problems*_\n",
    "\n",
    "Here we consider a simplified graph partition problem.\n",
    "Consider a graph $G = (V, E)$, where $V$ denotes the set of n vertices and $E$ the set of edges. \n",
    "The objective of graph partition is to partition $G$ into two sets of the same size (let us assume we have even number of vertices), \n",
    "while minimizing the capacity of the edges across the two sets.\n",
    "\n",
    "We will go through two examples to show:\n",
    "1. How to run the optimization\n",
    "2. How how to run the optimization with the VQE.\n",
    "\n",
    "Note the objective_value below is defined as the the number of crossing edges. The goal is to minimize this value.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method\n",
    "\n",
    "The graph involved in our example is as follows. The graph is in the adjacent matrix form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  4.  5.  3.]\n",
      " [ 4.  0. -5.  7.]\n",
      " [ 5. -5.  0.  0.]\n",
      " [ 3.  7.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from qiskit import BasicAer\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising import graph_partition\n",
    "from qiskit.optimization.applications.ising.common import random_graph, sample_most_likely\n",
    "\n",
    "np.random.seed(100)\n",
    "num_nodes = 4\n",
    "w = random_graph(num_nodes, edge_prob=0.8, weight_range=10)\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is in the first partition) or 1 (meaning the vertex is in the second partition). We print the binary assignment that satisfies the definition of the graph partition and corresponds to the minimial number of crossing edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value computed by the brute-force method is 3\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # use the brute-force way to generate the oracle\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = num_nodes\n",
    "    max = 2**L\n",
    "    minimal_v = np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "\n",
    "        how_many_nonzero = np.count_nonzero(cur)\n",
    "        if how_many_nonzero * 2 != L:  # not balanced\n",
    "            continue\n",
    "\n",
    "        cur_v = graph_partition.objective_value(np.array(cur), w)\n",
    "        if cur_v < minimal_v:\n",
    "            minimal_v = cur_v\n",
    "    return minimal_v\n",
    "\n",
    "sol = brute_force()\n",
    "print(\"Objective value computed by the brute-force method is\", sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = graph_partition.get_operator(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 1 0 1]\n",
      "Objective value computed by the NumPyMinimumEigensolver is 3\n"
     ]
    }
   ],
   "source": [
    "algo = NumPyMinimumEigensolver(qubit_op, aux_operators=[])\n",
    "result = algo.run()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "print(ising_sol)\n",
    "print(\"Objective value computed by the NumPyMinimumEigensolver is\", graph_partition.objective_value(x, w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization with the VQE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 1. 0. 1.]\n",
      "Objective value computed by VQE is 3.0\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "# check against the oracle\n",
    "ising_sol = graph_partition.get_graph_solution(x)\n",
    "print(ising_sol)\n",
    "print(\"Objective value computed by VQE is\", graph_partition.objective_value(x, w))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
